`
https://leetcode.cn/problems/find-k-closest-elements/
`

/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
var findClosestElements = function (arr, k, x) {
  // 先找到 x 在数组中的位置
  const p = leftBound(arr, x)
  // 两端都开的区间 (left, right)
  let left = p - 1, right = p
  const res = []

  // 如果区间内长度小于 k
  while (right - left - 1 < k) {
    // 如果左边没元素了
    if (left === -1) res.push(arr[right++])
    // 如果右边没有元素了
    else if (right === arr.length) res.unshift(arr[left--])
    // 两边同时有元素，先加小的
    else if (x - arr[left] > arr[right] - x) res.push(arr[right++])
    else res.unshift(arr[left--])
  }

  return res
};

function leftBound(arr, target) {
  let left = 0, right = arr.length - 1
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
    if (arr[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return left
}